package com.krahets88.stack;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Question295 {
    @Test
    public void test1() {
        MedianFinder1 finder1 = new MedianFinder1();
        finder1.addNum(-1);
        System.out.println(finder1.findMedian());
        finder1.addNum(-2);
        System.out.println(finder1.findMedian());
        finder1.addNum(-3);
        System.out.println(finder1.findMedian());
        finder1.addNum(-4);
        System.out.println(finder1.findMedian());
        finder1.addNum(-5);
        System.out.println(finder1.findMedian());
    }
    @Test
    public void test2(){
        MedianFinder2 finder2 = new MedianFinder2();
        finder2.addNum(-1);
        System.out.println(finder2.findMedian());
        finder2.addNum(-2);
        System.out.println(finder2.findMedian());
        finder2.addNum(-3);
        System.out.println(finder2.findMedian());
        finder2.addNum(-4);
        System.out.println(finder2.findMedian());
        finder2.addNum(-5);
        System.out.println(finder2.findMedian());
    }
}

class MedianFinder1 {
    List<Integer> list;

    public MedianFinder1() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        /*
        使用二分查找，找出插入的位置
         */
        if (!list.isEmpty()) {
            int i = 0, j = list.size() - 1, mid = 0, index = -1;
            while (i <= j) {
                mid = i + (j - i) / 2;
                if (num > list.get(mid)) {
                    i = mid + 1;
                } else if (num < list.get(mid)) {
                    j = mid - 1;
                } else {
                    i = mid + 1;
                }
            }
            if (index == -1) {
                index = i;
            }
            list.add(index, num);
        } else {
            list.add(num);
        }

    }

    public double findMedian() {
        if (list.size() % 2 == 0) {
            int index = list.size() / 2;
            return (double) (list.get(index) + list.get(index - 1)) / 2;
        } else {
            return (double) list.get(list.size() / 2);
        }
    }
}
class MedianFinder2 {
    /**
     * 学会如何用两个堆来求中位数
     */
    Queue<Integer> bigHeap;     //大根堆 存储小的一半元素
    Queue<Integer> smallHeap;   // 默认小根堆，存储大的一半

    public MedianFinder2() {
        smallHeap = new PriorityQueue<>();
        bigHeap = new PriorityQueue<>((a, b) -> (b - a));
    }

    /**
     * 大根堆的元素可以大于小根堆的元素大于1
     *
     * @param num
     */
    public void addNum(int num) {
        if(smallHeap.size()>0 && bigHeap.size()>0&&(num > smallHeap.peek())){
            // 如果元素已经比大元素最小的大了，需要调换位置
                bigHeap.add(smallHeap.remove());
                smallHeap.add(num);
        }else{
            bigHeap.add(num);
        }
        while (bigHeap.size() - smallHeap.size() > 1) {
            smallHeap.add(bigHeap.remove());
        }
    }

    public double findMedian() {
        if ((bigHeap.size() + smallHeap.size()) % 2 == 0) {
            // 偶数项
            double double_value =  (double)(bigHeap.peek()+smallHeap.peek())/2;
            return double_value;
        } else {
            // 奇数项
            int  double_value = bigHeap.peek();
            return double_value;
        }
    }
}
class MedianFinder3 {
    /**
     * 学会如何用两个堆来求中位数
     */
    Queue<Integer> bigHeap;     //大根堆 存储小的一半元素
    Queue<Integer> smallHeap;   // 默认小根堆，存储大的一半

    public MedianFinder3() {
        smallHeap = new PriorityQueue<>();
        bigHeap = new PriorityQueue<>((a, b) -> (b - a));
    }

    /**
     * 大根堆的元素可以大于小根堆的元素大于1，也就是说如果
     * 1.大根堆元素数=小根堆元素数 则大根堆内的元素要添加小根堆的堆顶元素
     * 2.大根堆元素数>小根堆元素数 则小根堆内的元素要添加大根堆的堆顶元素
     * 注意：为了保持大根堆 小根堆维护的分别是小的一半和大的一半，
     * 1.添加元素到大根堆时，必须先入小根堆，将最小的元素添加到大根堆
     * 2.添加元素到小根堆时，必须先入大根堆，将最大的元素添加到小根堆
     *
     * @param num
     */
    public void addNum(int num) {
        if(bigHeap.size()==smallHeap.size()){
            smallHeap.add(num);
            bigHeap.add(smallHeap.remove());
        }else {
            bigHeap.add(num);
            smallHeap.add(bigHeap.remove());
        }
    }

    public double findMedian() {
        if ((bigHeap.size() + smallHeap.size()) % 2 == 0) {
            // 偶数项
            double double_value =  (double)(bigHeap.peek()+smallHeap.peek())/2;
            return double_value;
        } else {
            // 奇数项
            int  double_value = bigHeap.peek();
            return double_value;
        }
    }
}
